#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 718. 最长重复子数组.py
@time: 2022/1/20 13:46
@desc: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
> 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

@解题思路：
    1. dp, dp[i][j]表示nums1前i个和num2前j个的最长公共前缀，计算dp[i][j]要对比nums1[i-1]=?=nums2[j-1]
    2. 参考：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zhe-yao-jie-shi-ken-ding-jiu-dong-liao-by-hyj8/
    3. Ot(nm), Os(nm)
'''
class Solution(object):
    def findLength(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        m, n = len(nums1), len(nums2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        ans = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if nums1[i-1]==nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                ans = max(ans, dp[i][j])

        return ans

if __name__ == '__main__':
    num1 = [1,2,3,2,1]
    num2 = [3,2,1,4]
    ans = Solution().findLength(num1, num2)
    print(ans)